home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / russell / gc32.lha / headers.c < prev    next >
C/C++ Source or Header  |  1993-07-15  |  7KB  |  270 lines
  1. /* 
  2.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  3.  * Copyright (c) 1991-1993 by Xerox Corporation.  All rights reserved.
  4.  *
  5.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  6.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  7.  *
  8.  * Permission is hereby granted to copy this garbage collector for any purpose,
  9.  * provided the above notices are retained on all copies.
  10.  */
  11.  
  12. /*
  13.  * This implements:
  14.  * 1. allocation of heap block headers
  15.  * 2. A map from addresses to heap block addresses to heap block headers
  16.  *
  17.  * Access speed is crucial.  We implement an index structure based on a 2
  18.  * level tree.
  19.  */
  20.  
  21. # include "gc_private.h"
  22.  
  23. bottom_index * GC_all_bottom_indices = 0;
  24.  
  25. /* Non-macro version of header location routine */
  26. hdr * GC_find_header(h)
  27. ptr_t h;
  28. {
  29. #   ifdef TL_HASH
  30.     register hdr * result;
  31.     GET_HDR(h, result);
  32.     return(result);
  33. #   else
  34.     return(HDR(h));
  35. #   endif
  36. }
  37.  
  38. /* Routines to dynamically allocate collector data structures that will */
  39. /* never be freed.                             */
  40.  
  41. static ptr_t scratch_free_ptr = 0;
  42.  
  43. static ptr_t scratch_end_ptr = 0;
  44.  
  45. ptr_t GC_scratch_alloc(bytes)
  46. register word bytes;
  47. {
  48.     register ptr_t result = scratch_free_ptr;
  49.     scratch_free_ptr += bytes;
  50.     if (scratch_free_ptr <= scratch_end_ptr) {
  51.         return(result);
  52.     }
  53.     {
  54.         word bytes_to_get = HINCR * HBLKSIZE;
  55.          
  56.         if (bytes_to_get <= bytes) {
  57.           /* Undo the damage, and get memory directly */
  58.             scratch_free_ptr -= bytes;
  59.             return((ptr_t)GET_MEM(bytes));
  60.         }
  61.         scratch_free_ptr = (ptr_t)GET_MEM(bytes_to_get);
  62.         if (scratch_free_ptr == 0) {
  63. #        ifdef PRINTSTATS
  64.                 GC_printf0("Out of memory - trying to allocate less\n");
  65. #        endif
  66.             result = (ptr_t)GET_MEM(bytes);
  67.             if (result == 0) {
  68.                 return(0);
  69.             } else {
  70.                 scratch_free_ptr -= bytes;
  71.                 return(result);
  72.             }
  73.         }
  74.         scratch_end_ptr = scratch_free_ptr + bytes_to_get;
  75.         return(GC_scratch_alloc(bytes));
  76.     }
  77. }
  78.  
  79. static hdr * hdr_free_list = 0;
  80.  
  81. /* Return an uninitialized header */
  82. static hdr * alloc_hdr()
  83. {
  84.     register hdr * result;
  85.     
  86.     if (hdr_free_list == 0) {
  87.         result = (hdr *) GC_scratch_alloc((word)(sizeof(hdr)));
  88.     } else {
  89.         result = hdr_free_list;
  90.         hdr_free_list = (hdr *) (result -> hb_next);
  91.     }
  92.     return(result);
  93. }
  94.  
  95. static void free_hdr(hhdr)
  96. hdr * hhdr;
  97. {
  98.     hhdr -> hb_next = (struct hblk *) hdr_free_list;
  99.     hdr_free_list = hhdr;
  100. }
  101.  
  102. GC_init_headers()
  103. {
  104.     register int i;
  105.      
  106.     for (i = 0; i < TOP_SZ; i++) {
  107.         GC_top_index[i] = &GC_all_nils;
  108.     }
  109. }
  110.  
  111. /* Make sure that there is a bottom level index block for address addr  */
  112. /* Return FALSE on failure.                        */
  113. static bool get_index(addr)
  114. register word addr;
  115. {
  116.     register word hi =
  117.             (word)(addr) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE);
  118.     register bottom_index * r;
  119.     register bottom_index * p;
  120.     register bottom_index ** prev;
  121. #   ifdef HASH_TL
  122.       register i = TL_HASH(hi);
  123.       register bottom_index * old;
  124.       
  125.       old = p = GC_top_index[i];
  126.       while(p != &GC_all_nils) {
  127.           if (p -> key == hi) return(TRUE);
  128.           p = p -> hash_link;
  129.       }
  130.       r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index)));
  131.       if (r == 0) return(FALSE);
  132.       bzero((char *)r, (int)(sizeof (bottom_index)));
  133.       r -> hash_link = old;
  134.       GC_top_index[i] = r;
  135. #   else
  136.       if (GC_top_index[hi] != &GC_all_nils) return(TRUE);
  137.       r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index)));
  138.       if (r == 0) return(FALSE);
  139.       GC_top_index[hi] = r;
  140.       bzero((char *)r, (int)(sizeof (bottom_index)));
  141. # endif
  142.     r -> key = hi;
  143.     /* Add it to the list of bottom indices */
  144.       prev = &GC_all_bottom_indices;
  145.       while ((p = *prev) != 0 && p -> key < hi) prev = &(p -> asc_link);
  146.       r -> asc_link = p;
  147.       *prev = r;
  148.     return(TRUE);
  149. }
  150.  
  151. /* Install a header for block h.  */
  152. /* The header is uninitialized.      */
  153. /* Returns FALSE on failure.      */
  154. bool GC_install_header(h)
  155. register struct hblk * h;
  156. {
  157.     hdr * result;
  158.     
  159.     if (!get_index((word) h)) return(FALSE);
  160.     result = alloc_hdr();
  161.     SET_HDR(h, result);
  162.     return(result != 0);
  163. }
  164.  
  165. /* Set up forwarding counts for block h of size sz */
  166. bool GC_install_counts(h, sz)
  167. register struct hblk * h;
  168. register word sz; /* bytes */
  169. {
  170.     register struct hblk * hbp;
  171.     register int i;
  172.     
  173.     for (hbp = h; (char *)hbp < (char *)h + sz; hbp += BOTTOM_SZ) {
  174.         if (!get_index((word) hbp)) return(FALSE);
  175.     }
  176.     if (!get_index((word)h + sz - 1)) return(FALSE);
  177.     for (hbp = h + 1; (char *)hbp < (char *)h + sz; hbp += 1) {
  178.         i = HBLK_PTR_DIFF(hbp, h);
  179.         SET_HDR(hbp, (hdr *)(i > MAX_JUMP? MAX_JUMP : i));
  180.     }
  181.     return(TRUE);
  182. }
  183.  
  184. /* Remove the header for block h */
  185. void GC_remove_header(h)
  186. register struct hblk * h;
  187. {
  188.     hdr ** ha;
  189.     
  190.     GET_HDR_ADDR(h, ha);
  191.     free_hdr(*ha);
  192.     *ha = 0;
  193. }
  194.  
  195. /* Remove forwarding counts for h */
  196. void GC_remove_counts(h, sz)
  197. register struct hblk * h;
  198. register word sz; /* bytes */
  199. {
  200.     register struct hblk * hbp;
  201.     
  202.     for (hbp = h+1; (char *)hbp < (char *)h + sz; hbp += 1) {
  203.         SET_HDR(hbp, 0);
  204.     }
  205. }
  206.  
  207. /* Apply fn to all allocated blocks */
  208. /*VARARGS1*/
  209. void GC_apply_to_all_blocks(fn, client_data)
  210. void (*fn)(/* struct hblk *h, word client_data */);
  211. word client_data;
  212. {
  213.     register int j;
  214.     register bottom_index * index_p;
  215.     
  216.     for (index_p = GC_all_bottom_indices; index_p != 0;
  217.          index_p = index_p -> asc_link) {
  218.         for (j = BOTTOM_SZ-1; j >= 0;) {
  219.             if (!IS_FORWARDING_ADDR_OR_NIL(index_p->index[j])) {
  220.                 if (index_p->index[j]->hb_map != GC_invalid_map) {
  221.                     (*fn)(((struct hblk *)
  222.                             (((index_p->key << LOG_BOTTOM_SZ) + (word)j)
  223.                              << LOG_HBLKSIZE)),
  224.                           client_data);
  225.                 }
  226.                 j--;
  227.              } else if (index_p->index[j] == 0) {
  228.                 j--;
  229.              } else {
  230.                 j -= (int)(index_p->index[j]);
  231.              }
  232.          }
  233.      }
  234. }
  235.  
  236. /* Get the next valid block whose address is at least h    */
  237. /* Return 0 if there is none.                */
  238. struct hblk * GC_next_block(h)
  239. struct hblk * h;
  240. {
  241.     register bottom_index * bi;
  242.     register word j = ((word)h >> LOG_HBLKSIZE) & (BOTTOM_SZ-1);
  243.     
  244.     GET_BI(h, bi);
  245.     if (bi == &GC_all_nils) {
  246.         register int hi = (word)h >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE);
  247.         bi = GC_all_bottom_indices;
  248.         while (bi != 0 && bi -> key < hi) bi = bi -> asc_link;
  249.         j = 0;
  250.     }
  251.     while(bi != 0) {
  252.         while (j < BOTTOM_SZ) {
  253.             if (IS_FORWARDING_ADDR_OR_NIL(bi -> index[j])) {
  254.                 j++;
  255.             } else {
  256.                 if (bi->index[j]->hb_map != GC_invalid_map) {
  257.                     return((struct hblk *)
  258.                             (((bi -> key << LOG_BOTTOM_SZ) + j)
  259.                              << LOG_HBLKSIZE));
  260.                 } else {
  261.                     j += divHBLKSZ(bi->index[j] -> hb_sz);
  262.                 }
  263.             }
  264.         }
  265.         j = 0;
  266.         bi = bi -> asc_link;
  267.     }
  268.     return(0);
  269. }
  270.